package bfsAndDfs

/*
时间复杂度：O（V+E） V为边数，E为节点数
空间复杂度：O(V+E)
 */

// BFS
func minimumSemesters(n int, relations [][]int) int {
	var (
		edges    = make([][]int, n)
		inDegree = make([]int, n)
		queue    []int
		// 存储拓扑排序结果
		result []int
		count  int
	)

	// 构建邻接表, 将编号1～N的节点变成编号0～n-1
	for _, info := range relations {
		// info[0] -> info[1]
		edges[info[0]-1] = append(edges[info[0]-1], info[1]-1)
		// 入度+1
		inDegree[info[1]-1]++
	}

	// 将度数为0的节点存入queue
	for i, v := range inDegree {
		if v == 0 {
			queue = append(queue, i)
		}
	}

	for len(queue) != 0 {
		// 统计完成所有课程需要的学期数
		count++
		// 将所有入度为0的节点一次性去除
		n := len(queue)
		for i := 0; i < n; i++ {
			e := queue[0]
			queue = queue[1:]
			// 存储拓扑排序结果
			result = append(result, e)
			// 遍历节点e的邻接节点
			for _, v := range edges[e] {
				inDegree[v]--
				// 将新的入度为0的节点存入队列
				if inDegree[v] == 0 {
					queue = append(queue, v)
				}
			}
		}
	}
	if len(result) != n {
		return -1
	}
	return count
}
